<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            思路：解数独和N皇后类似，但是有区别！！！N皇后每行只能放一个！！集合是列，判断这层能不能放即可。
            因此解数独需要二维for循环＋递归，这样才能确定当前位置

            终止条件：类似于N皇后，组合，都是有多个结果的。当然，解数独也有多个结果，但是，它保证解集只有一个，所以每次只需要遍历到
            叶子节点就可以直接返回true。不需要res.push()。所以也不需要终止条件了，只有到叶子节点就结束

            */
            var solveSudoku = function (board) {
                //不需要终止条件
                function backTracking(board) {
                    for (let i = 0; i < board.length; i++) {
                        for (let j = 0; j < board[0].length; j++) {
                            if (board[i][j] != '.') continue
                            //如果遇到了空位,通过条件判断放入哪个
                            for (let k = 1; k <= 9; k++) {
                                if (isValid(i, j, `${k}`)) {
                                    board[i][j] = `${k}`
                                    if (backTracking(board)) {
                                        //如果递归后的结果是true，即找到了一组 那么就立刻返回true
                                        return true
                                    }
                                    //回溯
                                    board[i][j] = '.'
                                }
                            }
                            //尝试了9个数都不行，return false
                            return false
                        }
                    }
                    //最后遍历完了没有返回false，说明找到了何时棋盘位置
                    return true
                }

                function isValid(row, col, k) {
                    //判断一行中是否有重复  总共9行9列
                    for (let i = 0; i < 9; i++) {
                        if (board[row][i] == k) {
                            return false
                        }
                    }
                    for (let j = 0; j < 9; j++) {
                        if (board[j][col] == k) {
                            return false
                        }
                    }
                    //判断九方格内是否重复。数独分为9个小九方格
                    let startRow = Math.floor(row / 3) * 3
                    let startCol = Math.floor(col / 3) * 3
                    for (let i = startRow; i < startRow + 3; i++) {
                        for (let j = startCol; j < startCol + 3; j++) {
                            if (board[i][j] == k) {
                                return false
                            }
                        }
                    }
                    return true
                }
                backTracking(board)
                return board
            }
        </script>
    </body>
</html>
